package ar.com.utn.openqsb.lip.core;

import java.text.DecimalFormat;
import java.util.List;
import java.util.Map;

import org.apache.commons.math.linear.RealMatrix;
import org.apache.commons.math.linear.RealMatrixImpl;
import org.apache.commons.math.linear.RealVector;
import org.apache.commons.math.linear.RealVectorImpl;

import ar.com.utn.openqsb.lip.core.Constraint.Relation;
import ar.com.utn.openqsb.lip.core.Objective.Type;

/**
 * A tableau for use in the Simplex method.<br>
 * Example:<br>
 * <code>
 *   W |  Z |  x1 |  x2 |  x- | s1 |  s2 |  a1 |  RHS<br>
 * ---------------------------------------------------<br>
 * 	-1		0		0		0		0		0		0		1		0		<= phase 1 objective<br>
 * 	0		1		-15	-10	0		0		0		0		0		<= phase 2 objective<br>
 * 	0		0		1		0		0		1		0		0		2		<= constraint 1<br>
 * 	0		0		0		1		0		0		1		0		3		<= constraint 2<br>
 * 	0		0		1		1		0		0		0		1		4		<= constraint 3<br>
 * </code><br>
 * W: Phase 1 objective function<br>
 * Z: Phase 2 objective function<br>
 * x1 & x2: Decision variables<br>
 * x-: Extra decision variable to allow for negative values<br>
 * s1 & s2: Slack/Surplus variables<br>
 * a1: Artificial variable<br>
 * RHS: Right hand side<br>
 * <br>
 * 
 * @author rvega based on <a href="http://www.benmccann.com">Ben McCann's</a>
 *         work
 */
public class SimplexMatrix
{

    private RealMatrix matrix;

    private boolean nonNegative;
    private int numDecisionVariables;
    private int numSlackVariables;
    private int numArtificialVariables;
    private int numObjectiveFunctions;
    private int decisionVariableOffset;
    private int slackVariableOffset;
    private int artificialVariableOffset;

    private SimplexModel model;

    public SimplexMatrix(SimplexModel model)
    {
        this(model, false);
    }

    public SimplexMatrix(SimplexModel model, boolean restrictToNonNegative)
    {
        this.model = model;

        List<Constraint> constraints = model.getNormalizedConstraints();
        Map<Relation, Integer> counts = model.getConstraintTypeCounts();
        nonNegative = restrictToNonNegative;
        numDecisionVariables = model.getNumVars() + (nonNegative ? 0 : 1);
        numSlackVariables = counts.get(Relation.LE) + counts.get(Relation.GE);
        numArtificialVariables = counts.get(Relation.EQ) + counts.get(Relation.GE);
        numObjectiveFunctions = numArtificialVariables > 0 ? 2 : 1;
        decisionVariableOffset = numObjectiveFunctions;
        slackVariableOffset = numObjectiveFunctions + numDecisionVariables;
        artificialVariableOffset = numObjectiveFunctions + numDecisionVariables + numSlackVariables;

        // create a matrix of the correct size
        // width + 1 is for right values
        int width = numDecisionVariables + numSlackVariables + numArtificialVariables + numObjectiveFunctions + 1;
        int height = constraints.size() + numObjectiveFunctions;
        double[][] matrix = new double[height][width];

        // initialize the objective function rows
        Objective objectiveFunction = model.getObjective();
        if (numObjectiveFunctions == 2)
        {
            matrix[0][0] = -1;
        }
        int zIndex = numObjectiveFunctions == 1 ? 0 : 1;
        boolean maximize = objectiveFunction.getType() == Type.MAXIMIZE;
        matrix[zIndex][zIndex] = maximize ? 1 : -1;
        RealVector objectiveCoefficients = maximize ? model.getObjective().getCoefficients().mapMultiply(-1) : model.getObjective().getCoefficients();
        System.arraycopy(objectiveCoefficients.getData(), 0, matrix[zIndex], decisionVariableOffset, objectiveCoefficients.getData().length);
        matrix[zIndex][width - 1] = maximize ? model.getObjective().getConstantTerm() : -1 * model.getObjective().getConstantTerm();

        if (!nonNegative)
        {
            matrix[zIndex][slackVariableOffset - 1] = getInvertedCoeffiecientSum(objectiveCoefficients);
        }

        // initialize the constraint rows
        int slackVar = 0;
        int artificialVar = 0;
        for (int i = 0; i < constraints.size(); i++)
        {
            Constraint constraint = constraints.get(i);
            int row = numObjectiveFunctions + i;

            // decision variable coefficients
            System.arraycopy(constraint.getCoefficients().getData(), 0, matrix[row], numObjectiveFunctions, constraint.getCoefficients().getData().length);

            // x-
            if (!nonNegative)
            {
                matrix[row][slackVariableOffset - 1] = getInvertedCoeffiecientSum(constraint.getCoefficients());
            }

            // RHS
            matrix[row][width - 1] = constraint.getRightValue();

            // slack variables
            if (constraint.getRelation() == Relation.LE)
            {
                matrix[row][slackVariableOffset + slackVar++] = 1; // slack
            } else if (constraint.getRelation() == Relation.GE)
            {
                matrix[row][slackVariableOffset + slackVar++] = -1; // excess
            }

            // artificial variables
            if (constraint.getRelation() == Relation.EQ || constraint.getRelation() == Relation.GE)
            {
                matrix[0][artificialVariableOffset + artificialVar] = 1;
                matrix[row][artificialVariableOffset + artificialVar++] = 1;
            }
        }

        this.matrix = new RealMatrixImpl(matrix);

        initialize();
    }

    /**
     * Puts the matrix in proper form by zeroing out the artificial variables in
     * the objective function via elementary row operations.
     */
    private void initialize()
    {
        for (int artificialVar = 0; artificialVar < numArtificialVariables; artificialVar++)
        {
            int row = getBasicRow(artificialVariableOffset + artificialVar);
            subtractRow(0, row, 1.0);
        }
    }

    /**
     * Returns the current solution. {@link #solve} should be called first for
     * this to be the optimal solution.
     */
    public SimplexResult getSolution()
    {
        // get decision variable values
        double[] decisionVariableList = new double[getOriginalNumDecisionVariables()];
        double mostNegative = getDecisionVariableValue(getOriginalNumDecisionVariables());
        for (int i = 0; i < decisionVariableList.length; i++)
        {
            decisionVariableList[i] = nonNegative ? getDecisionVariableValue(i) : getDecisionVariableValue(i) - mostNegative;
            System.out.println("X" + i + ": " + decisionVariableList[i]);
        }

        // objective coefficients
        double[] objectiveCoefficientList = model.getObjective().getCoefficients().getData();

        // contribution
        RealVector variableContribution = new RealVectorImpl(decisionVariableList);
        variableContribution = variableContribution.ebeMultiply(objectiveCoefficientList);

        double value = matrix.getEntry(0, 0) * matrix.getEntry(0, getRhsOffset());
        System.out.println("Z: " + matrix.getEntry(0, 0) * matrix.getEntry(0, getRhsOffset()));

        Type objectiveType = model.getObjective().getType();

        // constraint details
        List<Constraint> constraints = model.getConstraints();
        Relation[] constraintRelationList = new Relation[constraints.size()];
        double[] constraintRHSList = new double[constraints.size()];
        double[] slackValueList = new double[constraints.size()];
        for (int i = 0; i < constraintRelationList.length; i++)
        {
            constraintRelationList[i] = constraints.get(i).getRelation();
            constraintRHSList[i] = constraints.get(i).getRightValue();
            slackValueList[i] = constraintRHSList[i] - constraints.get(i).getCoefficients().dotProduct(decisionVariableList);
        }
        

        return new SimplexResult(decisionVariableList, objectiveCoefficientList, variableContribution.getData(), value, objectiveType, constraintRelationList,
                constraintRHSList, slackValueList);
    }

    /**
     * Returns the value of the given decision variable. This is not the actual
     * value as it is guaranteed to be >= 0 and thus must be corrected before
     * being returned to the user.
     * 
     * @param decisionVariable
     *            The index of the decision variable
     * @return The value of the given decision variable.
     */
    private double getDecisionVariableValue(int decisionVariable)
    {
        Integer basicRow = getBasicRow(getNumObjectiveFunctions() + decisionVariable);
        return basicRow == null ? 0 : getEntry(basicRow, getRhsOffset());
    }

    /**
     * Checks whether the given column is basic.
     * 
     * @return the row that the variable is basic in. null if the column is not
     *         basic
     */
    private Integer getBasicRow(int col)
    {
        Integer row = null;
        for (int i = getNumObjectiveFunctions(); i < getHeight(); i++)
        {
            if (getEntry(i, col) != 0.0)
            {
                if (row == null)
                {
                    row = i;
                } else
                {
                    return null;
                }
            }
        }
        return row;
    }

    /**
     * Returns the -1 times the sum of all coefficients in the given array.
     */
    protected static double getInvertedCoeffiecientSum(RealVector coefficients)
    {
        double sum = 0;
        for (double coefficient : coefficients.getData())
        {
            sum -= coefficient;
        }
        return sum;
    }

    /**
     * Subtracts a multiple of one row from another. After application of this
     * operation, the following will hold: minuendRow = minuendRow - multiple *
     * subtrahendRow
     */
    public void divideRow(int dividendRow, double divisor)
    {
        for (int j = 0; j < getWidth(); j++)
        {
            matrix.setEntry(dividendRow, j, matrix.getEntry(dividendRow, j) / divisor);
        }
    }

    /**
     * Subtracts a multiple of one row from another. After application of this
     * operation, the following will hold: minuendRow = minuendRow - multiple *
     * subtrahendRow
     */
    public void subtractRow(int minuendRow, int subtrahendRow, double multiple)
    {
        for (int j = 0; j < getWidth(); j++)
        {
            matrix.setEntry(minuendRow, j, matrix.getEntry(minuendRow, j) - multiple * matrix.getEntry(subtrahendRow, j));
        }
    }

    /**
     * Removes the phase 1 objective function and artificial variables from this
     * tableau.
     */
    public void discardArtificialVariables()
    {
        if (numArtificialVariables == 0)
        {
            return;
        }
        int width = getWidth() - numArtificialVariables - 1;
        int height = getHeight() - 1;
        double[][] matrix = new double[height][width];
        for (int i = 0; i < height; i++)
        {
            for (int j = 0; j < width - 1; j++)
            {
                matrix[i][j] = getEntry(i + 1, j + 1);
            }
            matrix[i][width - 1] = getEntry(i + 1, getRhsOffset());
        }
        this.matrix = new RealMatrixImpl(matrix);
        this.numArtificialVariables = 0;
    }

    private final int getOriginalNumDecisionVariables()
    {
        return nonNegative ? numDecisionVariables : numDecisionVariables - 1;
    }

    public boolean hasArtificialVariables()
    {
        return numArtificialVariables != 0;
    }

    public double getEntry(int row, int column)
    {
        return matrix.getEntry(row, column);
    }

    public int getRhsOffset()
    {
        return matrix.getColumnDimension() - 1;
    }

    public int getNumObjectiveFunctions()
    {
        return numObjectiveFunctions;
    }

    public int getWidth()
    {
        return matrix.getColumnDimension();
    }

    public int getHeight()
    {
        return matrix.getRowDimension();
    }

    public void print(boolean initial)
    {
        if (initial)
        {
            System.out.println("Z\t\tx1\t\tx2\t\ts1\t\ts2\t\ts3\t\tRHS");
        } else
        {
            System.out.println("Z\t\tx1\t\tx2\t\ts1\t\ts2\t\ts3\t\tRHS");
        }
        DecimalFormat formatter = new DecimalFormat("#0.00");
        double[][] tmp = matrix.getData();
        for (int i = 0; i < tmp.length; i++)
        {
            for (int j = 0; j < tmp[i].length; j++)
            {
                System.out.print(formatter.format(tmp[i][j]) + "\t\t");
            }
            System.out.println();
        }
    }

}
